/*
* 思路：
* 借助队列，来遍历整个树
*
* 当前遍历这一层，都已经存入 thisLevelQueue 中，不为空时，一直出栈
* 出栈的节点，将值放入子列表，并将其子节点存入 subLevelQueue 中，
* thisLevelQueue 出栈完毕，将子列表存入 resultLists 中，并将 subLevelQueue 和 thisLevelQueue 替换
* 重新循环，直到 thisLevelQueue 无值可存
 */


import java.util.*;
import java.util.Queue;

public class Solution_1 {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> resultLists = new ArrayList<>();

        if(root==null)
        {
            return resultLists;
        }

        //TreeNode point = root;

        Queue<TreeNode> thisLevelQueue =new LinkedList<>();
        Queue<TreeNode> subLevelQueue = new LinkedList<>();

        List<Integer> innerList = new ArrayList<>();

        innerList.add(root.val);

        resultLists.add(innerList);

        thisLevelQueue.offer(root.left);
        thisLevelQueue.offer(root.right);

        TreeNode point = new TreeNode();

        innerList=new ArrayList<>();

        while(!thisLevelQueue.isEmpty())
        {
            point = thisLevelQueue.poll();
            if(point!=null)
            {
                innerList.add(point.val);
                subLevelQueue.offer(point.left);
                subLevelQueue.offer(point.right);
            }
            if(thisLevelQueue.isEmpty())
            {
                if(!innerList.isEmpty())
                resultLists.add(innerList);
                innerList=new ArrayList<>();
                thisLevelQueue=subLevelQueue;
                subLevelQueue=new LinkedList<>();
            }
        }
        return resultLists;

    }
}
